In an adhoc network system, communication terminals (referred to also as node apparatuses or simply as nodes) in an adhoc network autonomously connect to the network, and enable a mutual communication. The term “autonomously” means that a use does not need to set a communication route as occasion demands and a communication terminal or an infrastructure dedicated to management of communications of a server and a router is not needed.
As routing protocols of an adhoc network (adhoc protocols), Adhoc On Demand Distance Vector Algorithm (AODV) of a reactive type, and Optimized Link State Routing (OLSR) of a proactive type (OLSR) are known.
AODV is a technique with which communication node apparatus repeatedly broadcasts a packet by using broadcasting in order to search for a route and detects a route to target node apparatus. Communication node apparatus transmits a packet called “Route Request (RREQ)” to neighboring apparatuses in order to detect a target route. In this packet, a communication node ID of a detection target is explicitly described.
Neighboring communication node apparatus newly creates a RREQ packet when the local node apparatus is not searched, and repeatedly broadcasts the packet to neighboring communication node apparatuses. At this time, each of the communication node apparatuses records from which adjacent communication node apparatus a message addressed to a destination is received. When the RREQ message reaches target communication node apparatus, the target communication node apparatus creates a “Route Reply (PREP)” packet, and transmits the PREP packet so that the route on which the PREQ packet has been transmitted is traced. In this way, a bidirectional communication route is created.
With the OLSR, communication node apparatuses regularly exchange a packet, so that they grasp the entire network, and detect a route up to a target communication node. The communication node apparatuses regularly transmit a Hello packet, and each notify the counterpart that the local node apparatus resides. When the communication node apparatus, which will be a communication counterpart, is proved to reside, a path for flooding, which is called Multi Point Relay (MPR) and intended to efficiently deliver a packet to the entire network, is generated next. With the MPR, a packet can be efficiently broadcast from each communication node apparatus to the entire network. Next, the node apparatuses mutually deliver a Technology Control (TC) packet, which is a route generation message, by using this MPR, so that all node apparatuses can learn a network topology. To transmit a packet to target communication node apparatus, local communication node apparatus, which will be a source, references a network topology that the local communication node apparatus learns, and passes the packet to adjacent communication node apparatus to which the packet is to be transmitted. Also the adjacent node similarly executes the process. Finally, the packet is delivered to the target node apparatus.
Node apparatus that belongs to a wireless adhoc network uses a Hello packet in order to propagate routing information.
Assume that an adhoc network includes node apparatuses A and B. The node apparatus A generates a Hello packet including routing information that the local node apparatus holds, and regularly broadcasts the packet. The node apparatus B that has received the Hello packet makes a comparison between routing information that the local node apparatus holds and information included in the Hello packet, and obtains, from the Hello packet, routing information that the node apparatus B does not hold. Moreover, the node apparatus B also obtains quality information of a route from the Hello packet, and performs a communication by using a route having the highest possible quality. As described above, node apparatus that belongs to an adhoc network learns information of routes to other node apparatuses included in the network by using a Hello packet, and estimates an optimal route. Then, the node apparatus performs a communication by using the estimated optimal route. Each node apparatus included in the adhoc network holds, in a routing table, routes to all the other node apparatuses within the adhoc network. For example, the node apparatus A holds, in the routing table, information of routes to node apparatuses other than the local node apparatus within the adhoc network. Accordingly, the node apparatus A is able to transmit a data packet, for example, to node apparatus C via node apparatus B. Such node apparatus sometimes includes a weight table for storing weight information of a node, which is a relay destination for each final destination of a packet. In this case, the node apparatus identifies a node, which is to be a destination for relaying a packet, by referencing a weight table corresponding to the destination node of the packet when the node apparatus transfers the packet.
However, with the method by which each node apparatus holds, in a routing table, routes to all the other node apparatuses within an adhoc network, the size of the routing table increases as the number of node apparatuses within the network grows. Therefore, a method by which node apparatuses within a network are grouped into clusters and each of the node apparatuses stores, in a routing table, information of routes to node apparatuses within the same cluster is known.
There is a method using a control packet when a cluster is generated from node apparatuses within a network. For example, a cluster to which each node apparatus belongs is decided based on route information, and a control packet is transmitted and received when node apparatus participates in or departs from the cluster. Generally, when a cluster is formed, another cluster is generated when the number of nodes within the cluster exceeds a specified value. Also a method using not a control packet but a Hello packet is known.
There is a problem such that a load imposed on node apparatus is increased by a transmission/reception or a relay process of a control packet when the control packet is unicast or flooded to all node apparatuses within a network.
Additionally, a method for forming clusters by repeating a process of generating another cluster when the number of nodes within a cluster exceeds a specified value has a problem such that fluctuations in the number of clusters occur in the clusters depending on a layout of nodes. Namely, the number of clusters sometimes exceeds “the number of nodes within the entire network÷ an upper limit number of nodes within a cluster”. When this method is applied to a large-scale network including node apparatuses on the order of several thousands, the number of clusters straddled at the time of routing increases when the number of clusters grows, posing a problem of degradation of a throughput.    [Patent Document 1] International Publication Pamphlet No. 2006/067922